home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 3210 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  4.0 KB
  1. Path: cymbal.aix.calpoly.edu!not-for-mail
  2. From: dstubbs@cymbal.aix.calpoly.edu (Dan Stubbs)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Fastest way to computer log(base2) of x?
  5. Date: 26 Jan 1996 10:03:23 -0800
  6. Organization: California Polytechnic State University, San Luis Obispo
  7. Message-ID: <4eb51b$1d5r@cymbal.aix.calpoly.edu>
  8. References: <4e61iu$p6e@villa.fc.net>
  9. NNTP-Posting-User: dstubbs@cymbal.aix.calpoly.edu
  10.  
  11. In article <4e61iu$p6e@villa.fc.net>,
  12. Avinash Chopde <avinash@paranoia.com> wrote:
  13. >
  14. >I am trying to find out what could be the fastest way to compute
  15. >the position of the highest bit in any given integer -- basically, the
  16. >logarithm to the base 2 of any number.
  17. >
  18.    --[text deleted]
  19.  
  20. >Any thoughts or other ideas?
  21. >
  22. >Thanks!
  23. >
  24. >Avinash Chopde
  25. >e-mail: avinash@acm.org
  26. >home page: http://www.paranoia.com/~avinash/
  27.  
  28. Shown below is a plot of the relative times needed to find the highest
  29. bit as a function of the position of the target bit, and the search
  30. technique. Three search techniques were used and their implementations
  31. are given at the end of this post. The three techniques are
  32. (1) sequential search one bit at a time, (2) binary search, and 
  33. (3) sequential search four bits at a time followed by sequential
  34. search one bit at a time. Method (3) is fastest in almost every
  35. case--loosing to method (1) only when the highest bit is near the
  36. "left" end of the target value.
  37.  
  38. Time to find the left most bit in a 32 bit target value
  39. as a function of the target value. The target value
  40. is 2**k where k is shown as the value on the x axis
  41. below. For example 2**20 = 1,048,576. The three search 
  42. techniques reported are:
  43.  
  44.      S              S = sequential search.
  45.                     B = binary search.
  46.  50+                L = block search.
  47.    |     S          
  48.    |                The three implementations are
  49.    |                shown below.
  50.    |
  51.  40+
  52.    |           S
  53.    |
  54.   Time
  55.    |
  56.  30+                S
  57.    |
  58.    | B
  59.    |     B
  60.    |           B         S    
  61.  20+ L                   B    B
  62.    |     L          B               
  63.    |                               B
  64.    |           L              S
  65.    |                     L
  66.  10+                L         L      
  67.    |                               L
  68.    |                               S
  69.    |                                
  70.    |
  71.    +-----------------------------------  Value of k where
  72.      0   4     1    1    2    2    3     target value = 2**k.
  73.                0    5    0    5    0
  74.  
  75. int  lmb (int k) {
  76. /*   
  77.  *   returns the position of the left most bit in k assuming that
  78.  *      k > 0 and 32 bit ints. The algorithm used is a binary search.
  79.  */
  80.    unsigned left = 0, width = 16, mask = 0xffff0000;
  81.  
  82.    while (width > 1) {
  83.       if (k & mask) {
  84.          width /= 2;
  85.          mask <<= (left + width);
  86.          mask >>=  left;
  87.       }
  88.       else {
  89.          mask >>= width;
  90.          left +=  width;
  91.       }
  92.    } 
  93.    if (k & mask) return left;
  94.    else return left+1;
  95. }
  96.  
  97. int  lmb (int k) {
  98. /*   
  99.  *   returns the position of the left most bit in k assuming that
  100.  *      k > 0 and 32 bit ints. The algorithm used is a bit at a time
  101.  *      sequential search.
  102.  */
  103.    unsigned left = 0, mask = 0x80000000;
  104.  
  105.    while (!(k & mask)) {
  106.          mask >>=  1;
  107.          left++;
  108.    } 
  109.    return left;
  110. }
  111.  
  112. int  lmb (int k) {
  113. /*   
  114.  *   returns the position of the left most bit in k assuming that
  115.  *      k > 0 and 32 bit ints. The algorithm used uses two sequential
  116.  *      searchs. The first searches for the block of four bits
  117.  *      contianing the left most bit, and the second searches the
  118.  *      block found in the first search.
  119.  */
  120.    unsigned j=0, i=0;
  121.    static unsigned m1[] = {0xf0000000,0x0f000000,0x00f00000,0x000f0000,
  122.                              0x0000f000,0x00000f00,0x000000f0,0x0000000f};
  123.    static unsigned m2[] = {0x80000000,0x08000000,0x00800000,0x00080000,
  124.                              0x00008000,0x00000800,0x00000080,0x00000008};
  125.    unsigned mask;
  126.  
  127.    while (!(m1[j] & k)) ++j;
  128.    mask = m2[j];
  129.    while (!(mask & k)) {
  130.       mask >>= 1;
  131.       ++i;
  132.    }
  133.    return (4*j + i);
  134. }
  135.  
  136.